1. Field of Invention
The present invention generally relates to the field of machine learning, and more particularly relates to bounded optimization.
2. Description of Related Art
In the world of machine learning and related fields, penalized convex optimization is one of the most important topics of research. The penalties, or regularizations, imposed on the unconstrained convex cost function have largely been represented as L2-norm or L1-norm over a predicted vector. An alternative, but mathematically equivalent, approach is to cast the problem as a constrained optimization problem. In this setting, a minimizer of the objective function is constrained to have a bounded norm. A similar line of research has proposed a projection based regularization, wherein the convex function to be optimized is minimized without any constraint, and then the resultant sub-optimal solution is constrained to lie within the constrain space.
As it is known in the art, the L2-norm penalty imposes a smoothness constraint, and the L1-norm imposes sparsity constraint. Lately, sparse representations have been shown to be extremely efficient in encoding specific types of data, mainly, those obeying power decay law in some transform space such as the DCT. In an article entitled “For Most Large Under Determined Systems of Linear Equations the Minimal L1-norm Solution is Also the Sparsest Solution”, by Donoho, Comm. Pure Appl. Math, 59:797-829, 2004, Donoho provided sufficient conditions for obtaining an optimal L1-norm solution that is sparse. Recent work on compressed sensing has further explored how L1 constraints can be used for recovering a sparse signal sampled below the Nyquist rate.
L1 regularized maximum likelihood can be cast as a constrained optimization problem. Although standard algorithms such as interior-point methods offer powerful theoretical guarantees (e.g., polynomial-time complexity, ignoring the cost of evaluating the function), these methods typically require at each iteration the solution of a large, highly ill-conditioned linear system, which is potentially very difficult and expensive in terms of computing resources.